Benvenuti alla Lezione 3 di Concetti di Intelligenza Artificiale (PolyU COMP5511). In questa sessione, passiamo dal pathfinding di agenti singoli alla Ricerca Avversaria, in cui gli agenti operano in ambienti multi-agente competitivi. Introduciamo anche i Problemi di Soddisfacimento di Vincoli (CSP), un paradigma in cui l'obiettivo è trovare uno stato che soddisfi un insieme specifico di restrizioni piuttosto che un percorso.
Concetti Chiave
- Ricerca Avversaria: Si concentra su algoritmi come Minimax e Potatura Alpha-Beta per prendere decisioni razionali contro un avversario intelligente.
- Monte Carlo Tree Search (MCTS): Esplora il processo decisionale probabilistico, fungendo da spina dorsale per le moderne IA di gioco come AlphaGo.
- Soddisfacimento di Vincoli: Modella problemi utilizzando Variabili, Domini e Vincoli, risolti tramite Backtracking e Ricerca Locale.
Analisi della Complessità
Nelle impostazioni avversarie, la complessità dello spazio di ricerca è spesso definita dal fattore di diramazione del gioco
Avviso di Cambio di Paradigma
A differenza della ricerca standard (ad es. A* o BFS) in cui l'ambiente è statico, Ricerca Avversaria presuppone che l'ambiente (l'avversario) cerchi attivamente di minimizzare il tuo successo. Nei CSP, l'ordine delle azioni conta meno della validità dell'assegnazione finale.
Pseudocodice Concettuale: Tipi di Agente
1
# Agente Avversario (Teoria dei Giochi)
2
functionDecide_Move (state):
3
returnMaximize_Utility (Predict_Opponent_Minimization (state))
4
5
# Solutore CSP (Logica dei Vincoli)
6
functionSolve_CSP (variables, constraints):
7
ifAll_Constraints_Satisfied (assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search (variables)
Roadmap del Corso
Transizione dalla Ricerca (Lezione 2) al Processo Decisionale Strategico (Lezione 3).